package com.jacklei.tree;

import javafx.scene.transform.Rotate;

import java.util.LinkedList;
import java.util.Queue;

//完全二叉树
public class CompleteBinaryTree {
    static class Node{
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        Node root = new Node(1);

        root.left = new Node(2);
        root.right = new Node(3);

        root.left.left = new Node(4);
        root.left.right = new Node(5);

        root.right.left = new Node(6);
        root.right.right = new Node(7);

        System.out.println(check(root));
    }

    //判断是否为完全二叉树？
    public static boolean check(Node root) {
        if(root == null) return false;

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            Node poll = queue.poll();
            if(poll.left != null) { //左有
                queue.add(poll.left);
                if (poll.right != null) //右有
                    queue.add(poll.right);
                else   break;//右空

            } else
                if (poll.right != null) //左空右有
                        return false;
                else    break;//左空右空
        }
        while (!queue.isEmpty()){
            //下面都是叶子节点
            Node poll = queue.poll();
            if(poll.right != null || poll.left !=null)
                return false;
        }
        return true;
    }
}
